/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class test876 {
    public ListNode middleNode(ListNode head) {
        //快慢指针法
        //时间复杂度：O(N)，其中 N 是给定链表的结点数目。
        //
        //空间复杂度：O(1)，只需要常数空间存放 slow 和 fast 两个指针。
        //
        //如果头部为空，返回空
            if (head == null) {
                return null;
            }
            //定义快慢指针
            ListNode slow = head;
            ListNode fast = head;

            //当快指针不到链表末尾时，继续前进！
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            //当快指针结束时，满指针所指地址就是中间地址
            return slow;
        }

//    遍历算法
    //时间复杂度：O(N)，其中 N 是给定链表中的结点数目。
    //
    //空间复杂度：O(N)，即数组 A 用去的空间。
//    public ListNode middleNode(ListNode head) {
//        ListNode[] A = new ListNode[100];
//        int t = 0;
//        while (head != null) {
//            A[t++] = head;
//            head = head.next;
//        }
    //    t为最后一个链表的下表-1
//        return A[t / 2];
//    }

    //单指针空间优化：
    //时间复杂度：O(N)，其中 N 是给定链表的结点数目。
    //
    //空间复杂度：O(1)，只需要常数空间存放变量和指针。
//    class Solution {
//        public ListNode middleNode(ListNode head) {
//            int n = 0;
//            ListNode cur = head;
//            while (cur != null) {
//                ++n;
//                cur = cur.next;
//            }
//            int k = 0;
//            cur = head;
//            while (k < n / 2) {
//                ++k;
//                cur = cur.next;
//            }
//            return cur;
//        }
//    }
}
